Yoshiaki SHIRAISHI Toshihiro OHIGASHI Masakatu MORII
Knudsen et al. proposed an efficient method based on a tree-search algorithm with recursive process for reconstructing the internal state of RC4 stream cipher. However, the method becomes infeasible for word size n > 5 because its time complexity to reconstruct the internal state is too large. This letter proposes a more efficient method than theirs. Our method can reconstruct the internal state by using the pre-known internal-state entries, which are fewer than their method.
Youji FUKUTA Yoshiaki SHIRAISHI Masakatu MORII
A nonlinear combiner random number generator is a general keystream generator for certain stream ciphers. The generator is composed of several linear feedback shift registers and a nonlinear function; the output is used as a keystream. A fast correlation attack is a typical attack for such keystream generators. Mihaljevi, Fossorier, and Imai have proposed an improved fast correlation attack. The attack is based on error correction of information bits only in the corresponding binary linear block code; APP threshold decoding is employed for the error correction procedure. In this letter, we propose a method which improves the success rate of their attacks with similar complexity. The method adds some intentional error to original parity check equations. Those equations are then used in APP threshold decoding.
Miodrag J. MIHALJEVIC Hideki IMAI
It is shown that the effective secret-key size of TOYOCRYPT-HS1 stream cipher is only 96 bits, although the secret key consists of 128 bits. This characteristic opens a door for developing an algorithm for cryptanalysis based on the time-memory-data trade-off with the overall complexity significantly smaller than the exhaustive search over the effective key space.
Soichi FURUYA Dai WATANABE Yoichi SETO Kazuo TAKARAGI
In many cryptographic protocols, a common-key encryption is used to provide a secure data-transmission channel. More precisely, the general idea of protocols is to have an encryption provide data authenticity as well as data confidentiality. In fact, there are known to be quite a few ways to provide both forms of security, however none of them are optimized enough to be efficient. We present a new encryption mode that uses a random number generator (RNG). Assuming the security of the RNG, we can prove not only perfect secrecy, but also message authentication. The proven probability of a successful forgery is (n-1)/(2b-1), where b is the number of bits in a block and n is the number of ciphertext blocks. The proposed scheme achieves very high practicality due to the potential advantages in efficiency. When we use a computationally secure RNG, such as instance a pseudorandom number generator PRNG, we have advantages in efficiency; in addition to the PRNG parallel computation, the scheme requires only a single-path process on the data stream so that even a limited hardware resource can operate an encryption of a very long data stream. We demonstrate the practicality of our scheme, by showing a realistic parameter set and the evaluations of its performance.
NOR self-decimated sequences are attractive for stream ciphers because they have a good statistical property and the hardware construction is very simple. This paper presents an analysis of NOR self-decimation system for any parameter. We first determine the period. Then we show the exact distribution of consecutive two bits and three bits, which are shown to be almost uniform distribution.
Miodrag J. MIHALJEVIC Marc P. C. FOSSORIER Hideki IMAI
An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.
Two classes of nonlinear feedforward logic (NLFFL) pseudonoise (PN) code generators based on the use of AND and majority logic (ML) gates are compared. Cross-correlation and code-division multiple-access (CDMA) properties of properly designed NLFFL sequences are found to be comparable with the properties of well-known linear PN codes. It is determined that code design employing ML gates with an odd number of inputs is easier compared with designing with AND gates. This is especially true when the degree of nonlinearity is large, since the nonbalance problem, e. g. , at the output of an AND gate, can be avoided. ML type sequences are less vulnerable to correlation attack and jamming by the m-sequence of an NLFFL generator
Miodrag MIHALJEVIC Hideki IMAI
A novel family of keystream generators is proposed employing a linear cellular automata over GF (q) with time-varying transition rule. The analysis indicates that the generator, which is the general member of the family, reaches standard minimal security conditions (large period and good statistical properties) and that it is secure against all known attacks. An important feature of the proposed generators is that they are compact and suitable for high speed applications.